Leetcode 排好序的数组合并求中位数(复杂度限制O(log (m+n)))

发表于 | 分类于 | | 阅读次数:
字数统计: 185 | 阅读时长 ≈ 1

Leetcode

第四题
- There are two sorted arrays nums1 and nums2 of size m and n respectively.
1
- Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).


Solution:
思路：将俩个数组合并成sorted数组，找中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
'''
俩个数组排序合并，找中位数
'''
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        mergnums=[]
        i = 0
        j = 0
        print (len(nums1),len(nums2))
        nums1 = list(nums1)
        nums2 = list(nums2)
        while True:
            if nums1!=[] and nums2 !=[]:
                if nums1[i]<=nums2[j]:
                    mergnums.append(nums1[i])
                    del nums1[i]
                else:
                    mergnums.append(nums2[j])
                    del nums2[j]
                    print (j)            
            elif nums1 !=[] and nums2 ==[]:
                mergnums.append(nums1[i])
                del nums1[i]
            elif nums1 ==[] and nums2 !=[]:
                mergnums.append(nums2[j])
                del nums2[j]
            else:
                break  
        if (len(mergnums))%2 ==0:
            median = mergnums[int((len(mergnums)-2)/2)] + mergnums[int(len(mergnums)/2)]
            median = median/2.0
        else:
            median = mergnums[int(len(mergnums)/2)]
        return median

​
​